#include<iostream>
#include<time.h>
#include<stdio.h>
#include<sys/time.h>
#include<unistd.h>
using namespace std;
const int n=100;
int a[n];
void recursion(int);
int main(){
        double time1=0,time2=0,time3=0;
        for(int t=0;t<100;t++){
        int sum=0,sum1=0,sum2=0;
        for(int i=0;i<n;i++){
                a[i]=1;
        }

        struct  timeval  tv_begin,tv_end,tv_begin2,tv_end2,tv_begin3,tv_end3;
        gettimeofday(&tv_begin,NULL);
        for(int i=0;i<n;i++){//common
                sum+=a[i];
        }
        gettimeofday(&tv_end,NULL);
        time1+=(tv_end.tv_sec-tv_begin.tv_sec)*1000000+(tv_end.tv_usec-tv_begin.tv_usec);

        gettimeofday(&tv_begin2,NULL);
        for(int i=0;i<n;i+=2){//multilink
                sum1+=a[i];
                sum2+=a[i+1];
        }
        sum=sum1+sum2;
        gettimeofday(&tv_end2,NULL);
        time2+=(tv_end2.tv_sec-tv_begin2.tv_sec)*1000000+(tv_end2.tv_usec-tv_begin2.tv_usec);

        gettimeofday(&tv_begin3,NULL);
        recursion(n);//recursion
        sum=a[0];
        gettimeofday(&tv_end3,NULL);
        time3+=(tv_end3.tv_sec-tv_begin3.tv_sec)*1000000+(tv_end3.tv_usec-tv_begin3.tv_usec);

        }
        cout<<"common:"<<time1/100<<endl;
        cout<<"multiline:"<<time2/100<<endl;
        cout<<"recursion:"<<time3/100<<endl;

        return 0;
}
void recursion(int m){
        if(m==1)
                return;
        for(int i=0;i<m/2;i++)
                a[i]+=a[m-i-1];
        if(m%2==1)
                a[0]+=a[m/2];
        recursion(m/2);
        return;
}

